package shuanfa.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class MergeSort {
    public static void main(String[] args) {
        // arr=new int[]{3,4,6,7,2,7,2,8,0};
        int[] array = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array[i] = (int) (Math.random() * 80000);
        }
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(new Date());
        System.out.println("排序前时间：" + format);
        mergeSort(array, 0, array.length - 1, new int[array.length]);
        //System.out.println(Arrays.toString(arr));
        String format1 = simpleDateFormat.format(new Date());
        System.out.println("排序后的时间：" + format1);
    }

    private static void mergeSort(int[] array, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (right + left) / 2;
            //向左递归拆分
            mergeSort(array, left, mid, temp);
            //向右递归拆分
            mergeSort(array, mid + 1, right, temp);
            //合并
            merge(array, left, mid, right, temp);
        }
    }

    private static void merge(int[] array, int left, int mid, int right, int[] temp) {
        int i = left;//初始左边索引
        int j = mid + 1;//初始右边索引
        int t = 0;
        while (i <= mid && j <= right) {
            if (array[i] > array[j]) {
                temp[t++] = array[j++];//左边大就填充右边元素到临时数组
            } else {
                temp[t++] = array[i++];//右边大就填充左边元素到临时数组
            }
        }
        while (i <= mid) {//填充左边剩余元素到临时数组
            temp[t++] = array[i++];
        }
        while (j <= right) {//填充右边剩余元素到临时数组
            temp[t++] = array[j++];
        }
        //将临时数组拷贝到原数组
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            array[tempLeft++] = temp[t++];
        }
    }
}
